package com.tgy.algorithm.base._递归;

import java.util.Arrays;

/**
 * 假设有排成一行的N个位置，记为1~N，N一定大于或等于2
 * 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
 * 如果机器人来到1位置，那么下一步只能往右来到2位置;
 * 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置;
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走，
 * 规定机器人必须走K步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
 * 给定四个参数 N、M、K、P，返回方法数。
 */
public class _机器人走路 {


    /**
     *
     * @param n 总共1-到n个位置
     * @param m 在m位置
     * @param k 还剩下k步可以走
     * @param p 最终到达p
     * @return
     */
    public static int stepRun(int n,int m, int k,int p,int[][] cache) {
        if (k == 0) {
            // 走了k步，最终是否达到p
            return cache[m][k] = m == p ? 1: 0;
        }

        if (m == 1) {
            // m = 1 k
            return cache[m][k] = stepRun(n,2,k - 1,p,cache);
        }

        if (m == n) {

            return cache[m][k] = stepRun(n,n - 1,k - 1,p,cache);
        }

        return cache[m][k] = stepRun(n,m-1,k - 1,p,cache) + stepRun(n,m + 1, k - 1, p,cache);
    }

    public static void main(String[] args) {
        // 1,2,3,4,5,6

        int[][] cache = new int[6+1][4+1];
//        for (int i = 0; i < cache.length; i++) {
//            int[] line = cache[i];
//            for (int j=0;j < line.length;j++) {
//                System.out.println(line[j]);
//            }
//        }
        int stepCount = stepRun(6, 4, 4, 4,cache);
        System.out.println(stepCount);
    }
}
